package com.wx.datastructure.linked;

import java.util.Objects;

/**
 * @author wx
 * @Description: 链表实现
 * @date 2018/12/15 001518:55
 */
public class LinkedList<E> implements ILinked<E> {

    private Node node;
    private int size;


    @Override
    public int getSize() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return this.node == null || this.size == 0;
    }

    @Override
    public void addFirst(E e) {
        add(0, e);
    }

    @Override
    public void addLast(E e) {
        add(this.size, e);
    }

    @Override
    public void add(int index, E e) {
        validationAddIndex(index);
        if (index == 0) {
            this.node = new Node(e, this.node);
        } else {
            Node prev = this.node;
            for (int i = 1; i < index; i++) {
                prev = prev.next;
            }
            prev.next = new Node(e, prev.next);
        }

        size++;

    }

    @Override
    public E getFirst() {
        return get(0);
    }

    @Override
    public E getLast() {
        return get(this.size - 1);
    }

    @Override
    public E get(int index) {
        Node element = getByIndexNode(index);
        return element.e;
    }

    @Override
    public E removeFirst() {
        return remove(0);
    }

    @Override
    public E removeLast() {
        return remove(this.size - 1);
    }

    @Override
    public void removeElement(E e) {
        Node prev = this.node;
        Node upNode = null;
        while(prev != null){
            if(Objects.equals(prev.e,e)) {
                break;
            }
            prev = prev.next;
            upNode = prev;
        }

        if(prev != null){
            Node nextNode = prev.next;
            upNode.next = nextNode;
            //如果被删除节点内部引用类型没有被清除，那么这个对象无法被垃圾回收
            prev.next = null;
            size --;
        }
    }

    @Override
    public void set(int index, E e) {
        Node element = getByIndexNode(index);
        element.e = e;
    }

    @Override
    public boolean contains(E e) {
        return recursive(e,this.node) != null;
    }

    /**
     * @param index
     * @description: 验证下标是否合法
     * @author: wx
     * @date: 2018/12/15 0015
     * @return: void
     */
    private void validationIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index 不合法,index < 0 and index >= size");
        }
    }


    /**
     * @param index
     * @description: 验证下标是否合法
     * @author: wx
     * @date: 2018/12/15 0015
     * @return: void
     */
    private void validationAddIndex(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index 不合法,index < 0 and index >= size");
        }
    }

    /**
     * @param index
     * @description: 根据下标获取node节点
     * @author: wx
     * @date: 2018/12/15 0015
     * @return: com.wx.datastructure.linked.LinkedList<E>.Node
     */
    private Node getByIndexNode(int index) {
        validationIndex(index);
        Node element = this.node;
        for (int i = 1; i <= index; i++) {
            element = element.next;
        }
        return element;
    }


    /**
     * @param e
     * @description: 根据内容递归查询返回node节点
     * @author: wx
     * @date: 2018/12/15 0015
     * @return: com.wx.datastructure.linked.LinkedList<E>.Node
     */
    private Node recursive(E e, Node element) {
        if (element == null) {
            return null;
        }
        if (Objects.equals(e, element.e)) {
            return element;
        }
        return recursive(e, element.next);
    }

     /**
      * @description: 根据下标删除
      * @author: wx
      * @date: 2018/12/17 0017
      * @param index
      * @return: E
      */
     private E remove(int index){
        validationIndex(index);
        if (index == 0){
            Node firstNode = this.node;
            //如果被删除节点内部引用类型没有被清除，那么这个对象无法被垃圾回收
            this.node = this.node.next;
            firstNode.next = null;
            this.size --;
            return  firstNode.e;
        }else {
            Node element = this.node;
            for (int i = 1; i < index; i++){
                element = element.next;
            }
            Node retNode = element.next;
            element.next = retNode.next;
            //如果被删除节点内部引用类型没有被清除，那么这个对象无法被垃圾回收
            retNode.next = null;
            this.size --;
            return  element.e;
        }
     }


    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        Node prev = this.node;
        while (prev != null){
            res.append(prev.e).append("->");
            prev = prev.next;
        }
        return res.toString();
    }

    /**
     * @author wx
     * @Description: 节点对象
     * @date 2018-12-15
     */
    private class Node {
        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null, null);
        }

    }
}
